class ListNode:
    pred = None  # 前驱
    succ = None  # 后驱
    data = None  # 数据

    def __init__(self):
        super().__init__()

    def getPred(self):
        return self.pred

    def getSucc(self):
        return self.succ

    def data(self):
        return self.data

    def insertAsPred(self, e):
        newNode = ListNode()
        newNode.data = e
        newNode.pred = self.pred
        self.pred.succ = newNode
        newNode.succ = self
        self.pred = newNode
        return newNode

    def insertAsSucc(self, e):
        newNode = ListNode()
        newNode.data = e
        newNode.pred = self
        newNode.succ = self.succ
        self.succ.pred = newNode
        self.succ = newNode
        return newNode


class List:
    header = None
    trailer = None
    size = 0

    def __init__(self):
        super().__init__()
        self.header = ListNode()
        self.trailer = ListNode()
        self.header.succ = self.trailer
        self.trailer.pred = self.header
        self.size = 0

    def first(self):
        if self.size == 0:
            return None
        return self.header.getSucc()

    def last(self):
        if self.size == 0:
            return None
        return self.trailer.getPred()

    def insertAsFirst(self, e):
        self.size = self.size+1
        return self.header.insertAsSucc(e)

    def insertAsLast(self, e):
        self.size = self.size+1
        return self.trailer.insertAsPred(e)

    def insertBefore(self, p, e):
        self.size = self.size+1
        return p.insertAsPred(e)

    def insertAlter(self, p, e):
        self.size = self.size+1
        return p.insertAsSucc(e)

    def find(self, p):
        if size == 0:
            return None
        node = self.first()
        while node != self.trailer:
            if node.data == p:
                return
            node = node.sucee
        return Node

    def get(self, index):
        if index >= self.size:
            return None
        if index <= self.size >> 1:
            node = self.header.succ
            for i in range(index):
                node = node.succ
            return node
        else:
            node = self.trailer
            for i in range(self.size-index):
                node = node.pred
            return node
    def next(self,node):
        if node.succ == self.trailer:
            return None
        return node.succ

if __name__ == "__main__":
    list = List()
    for i in range(20):
        list.insertAsLast(i)

    print(list.size)
    print(list.get(0).data)
    print(list.get(2).data)
    print(list.get(10).data)
    print(list.get(12).data)
